package _动态规划系列._打家劫舍;

/**
 * @Author: 吕庆龙
 * @Date: 2020/4/1 19:44
 * <p>
 * 功能描述:
 */
public class Summary_0198 {

    /**
     * dp[i]: 从第1间到第i间房子抢到的最多的钱
     */
    public int rob1(int[] nums) {
        if(nums.length == 0)
            return 0;

        int n = nums.length;
        int[] dp = new int[n + 1];

        dp[0] = 0;
        dp[1] = nums[0];

        for (int i = 2; i < n + 1; i++) {
            dp[i] = Math.max(dp[i - 1]   //不抢，去下家
                    , nums[i - 1] + dp[i - 2]);  //抢，去下下家

        }
        return dp[n];
    }


    /**
     * dp[i]: 从第i间房子开始往后打劫房子(不包括第i间)，最多能抢到的钱
     *
     */
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 2];

        //base case 虽然java会默认初始化为0，但最好还是显示的写出来。
        dp[n] = 0;
        dp[n + 1] = 0;
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = Math.max(dp[i + 1]   //不抢，去下家
                    , nums[i] + dp[i + 2]);  //抢，去下下家
            //如果包括第i间，那么久应该是nums[i-1],不包括的话就是判断下一家
            //nums[i] 抢还是不抢。比如第2间房子，应该是nums[1],但实际上是nums[i]
        }
        return dp[0];
    }
}
